package com.leetcode.design;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/8/1 9:45
 */
public class LRUCache {

    private Map<Integer, Node> map;
    private int capacity;

    // 直接维护2个dummy结点，封装公共的方法
    private Node dummyHead, dummyTail;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        dummyHead = new Node(-1, -1);
        dummyTail = new Node(-1, -1);
        dummyHead.next = dummyTail;
        // 维系dummy结点，就不需要去判定是否为尾结点
        dummyTail.pre = dummyHead;
    }

    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        Node node = map.get(key);
        move2Head(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 直接更新原有的节点
            map.get(key).value = value;
            move2Head(map.get(key));
            return;
        }
        if (map.size() == capacity) {
            removeOldest();
        }
        Node node = new Node(key, value);
        map.put(node.key, node);
        add2Head(node);
    }

    // 对于公共的方法进行封装
    private void move2Head(Node node) {
        node.next.pre = node.pre;
        node.pre.next = node.next;
        add2Head(node);
    }

    private void add2Head(Node node) {
        Node oldHead = dummyHead.next;
        dummyHead.next = node;
        node.pre = dummyHead;
        node.next = oldHead;
        oldHead.pre = node;
    }

    private void removeOldest() {
        Node tail = dummyTail.pre;
        map.remove(tail.key);
        dummyTail.pre = tail.pre;
        tail.pre.next = dummyTail;
    }

    private static class Node {
        int key, value;

        Node pre, next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}
